home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 2: CDPD 1 / Almathera Ten on Ten - Disc 2: CDPD 1.iso / pd / 101-125 / 103 / avltrees / tree.c < prev    next >
C/C++ Source or Header  |  1995-03-13  |  10KB  |  512 lines
  1. /* as_tree - tree library for as
  2.  * vix 14dec85 [written]
  3.  * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
  4.  * vix 06feb86 [added tree_mung()]
  5.  * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
  6.  * vix 23jun86 [added delete uar to add for replaced nodes]
  7.  */
  8.  
  9.  
  10. /* This program text was created by Paul Vixie using examples from the book:
  11.  * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
  12.  * 0-13-022005-1.  This code and associated documentation is hereby placed
  13.  * in the public domain.
  14.  */
  15.  
  16.  
  17. /*#define        DEBUG    "tree"*/
  18.  
  19.  
  20. #include <stdio.h>
  21. #include "vixie.h"
  22. #include "tree.h"
  23.  
  24.  
  25. #ifdef DEBUG
  26. #define        MSG(msg)    printf("DEBUG: '%s'\n", msg);
  27. #else
  28. #define        MSG(msg)
  29. #endif
  30.  
  31.  
  32. void tree_init(ppr_tree)
  33. tree    **ppr_tree;
  34. {
  35.     ENTER("tree_init")
  36.     *ppr_tree = NULL;
  37.     EXITV
  38. }
  39.     
  40.  
  41. char *tree_srch(ppr_tree, pfi_compare, pc_user)
  42. tree    **ppr_tree;
  43. int    (*pfi_compare)();
  44. char    *pc_user;
  45. {
  46.     register int    i_comp;
  47.     register tree    *pr_new;
  48.  
  49.     ENTER("tree_srch")
  50.  
  51.     if (*ppr_tree)
  52.     {
  53.         i_comp = (*pfi_compare)(pc_user, (**ppr_tree).tree_p);
  54.         if (i_comp > 0)
  55.             EXIT(tree_srch(
  56.                 &(**ppr_tree).tree_r,
  57.                 pfi_compare,
  58.                 pc_user
  59.             ))
  60.         if (i_comp < 0)
  61.             EXIT(tree_srch(
  62.                 &(**ppr_tree).tree_l,
  63.                 pfi_compare,
  64.                 pc_user
  65.             ))
  66.  
  67.         /* not higher, not lower... this must be the one.
  68.          */
  69.         EXIT((**ppr_tree).tree_p)
  70.     }
  71.  
  72.     /* grounded. NOT found.
  73.      */
  74.     EXIT(NULL)
  75. }
  76.  
  77.  
  78. void tree_add(ppr_tree, pfi_compare, pc_user, pfi_delete)
  79. tree    **ppr_tree;
  80. int    (*pfi_compare)();
  81. char    *pc_user;
  82. int    (*pfi_delete)();
  83. {
  84.     void    sprout();
  85.     int    i_balance = FALSE;
  86.  
  87.     ENTER("tree_add")
  88.     sprout(ppr_tree, pc_user, &i_balance, pfi_compare, pfi_delete);
  89.     EXITV
  90. }
  91.  
  92.  
  93. static void sprout(ppr, pc_data, pi_balance, pfi_compare, pfi_delete)
  94. tree    **ppr;
  95. char    *pc_data;
  96. int    *pi_balance;
  97. int    (*pfi_compare)();
  98. int    (*pfi_delete)();
  99. {
  100.     tree    *p1, *p2;
  101.     int    cmp;
  102.  
  103.     ENTER("sprout")
  104.  
  105.     /* are we grounded?  if so, add the node "here" and set the rebalance
  106.      * flag, then exit.
  107.      */
  108.     if (!*ppr) {
  109.         MSG("grounded. adding new node, setting h=true")
  110.         *ppr = (tree *) malloc(sizeof(tree));
  111.         (*ppr)->tree_l = NULL;
  112.         (*ppr)->tree_r = NULL;
  113.         (*ppr)->tree_b = 0;
  114.         (*ppr)->tree_p = pc_data;
  115.         *pi_balance = TRUE;
  116.         EXITV
  117.     }
  118.  
  119.     /* compare the data using routine passed by caller.
  120.      */
  121.     cmp = (*pfi_compare)(pc_data, (*ppr)->tree_p);
  122.  
  123.     /* if LESS, prepare to move to the left.
  124.      */
  125.     if (cmp < 0) {
  126.         MSG("LESS. sprouting left.")
  127.         sprout(&(*ppr)->tree_l, pc_data, pi_balance,
  128.             pfi_compare, pfi_delete);
  129.         if (*pi_balance) {    /* left branch has grown longer */
  130.             MSG("LESS: left branch has grown")
  131.             switch ((*ppr)->tree_b)
  132.             {
  133.             case 1:    /* right branch WAS longer; balance is ok now */
  134.                 MSG("LESS: case 1.. balnce restored implicitly")
  135.                 (*ppr)->tree_b = 0;
  136.                 *pi_balance = FALSE;
  137.                 break;
  138.             case 0:    /* balance WAS okay; now left branch longer */
  139.                 MSG("LESS: case 0.. balnce bad but still ok")
  140.                 (*ppr)->tree_b = -1;
  141.                 break;
  142.             case -1:
  143.                 /* left branch was already too long. rebalnce */
  144.                 MSG("LESS: case -1: rebalancing")
  145.                 p1 = (*ppr)->tree_l;
  146.                 if (p1->tree_b == -1) {    /* LL */
  147.                     MSG("LESS: single LL")
  148.                     (*ppr)->tree_l = p1->tree_r;
  149.                     p1->tree_r = *ppr;
  150.                     (*ppr)->tree_b = 0;
  151.                     *ppr = p1;
  152.                 }
  153.                 else {            /* double LR */
  154.                     MSG("LESS: double LR")
  155.  
  156.                     p2 = p1->tree_r;
  157.                     p1->tree_r = p2->tree_l;
  158.                     p2->tree_l = p1;
  159.  
  160.                     (*ppr)->tree_l = p2->tree_r;
  161.                     p2->tree_r = *ppr;
  162.  
  163.                     if (p2->tree_b == -1)
  164.                         (*ppr)->tree_b = 1;
  165.                     else
  166.                         (*ppr)->tree_b = 0;
  167.  
  168.                     if (p2->tree_b == 1)
  169.                         p1->tree_b = -1;
  170.                     else
  171.                         p1->tree_b = 0;
  172.                     *ppr = p2;
  173.                 } /*else*/
  174.                 (*ppr)->tree_b = 0;
  175.                 *pi_balance = FALSE;
  176.             } /*switch*/
  177.         } /*if*/
  178.         EXITV
  179.     } /*if*/
  180.  
  181.     /* if MORE, prepare to move to the right.
  182.      */
  183.     if (cmp > 0) {
  184.         MSG("MORE: sprouting to the right")
  185.         sprout(&(*ppr)->tree_r, pc_data, pi_balance,
  186.             pfi_compare, pfi_delete);
  187.         if (*pi_balance) {    /* right branch has grown longer */
  188.             MSG("MORE: right branch has grown")
  189.  
  190.             switch ((*ppr)->tree_b)
  191.             {
  192.             case -1:MSG("MORE: balance was off, fixed implicitly")
  193.                 (*ppr)->tree_b = 0;
  194.                 *pi_balance = FALSE;
  195.                 break;
  196.             case 0:    MSG("MORE: balance was okay, now off but ok")
  197.                 (*ppr)->tree_b = 1;
  198.                 break;
  199.             case 1:    MSG("MORE: balance was off, need to rebalance")
  200.                 p1 = (*ppr)->tree_r;
  201.                 if (p1->tree_b == 1) {    /* RR */
  202.                     MSG("MORE: single RR")
  203.                     (*ppr)->tree_r = p1->tree_l;
  204.                     p1->tree_l = *ppr;
  205.                     (*ppr)->tree_b = 0;
  206.                     *ppr = p1;
  207.                 }
  208.                 else {            /* double RL */
  209.                     MSG("MORE: double RL")
  210.  
  211.                     p2 = p1->tree_l;
  212.                     p1->tree_l = p2->tree_r;
  213.                     p2->tree_r = p1;
  214.  
  215.                     (*ppr)->tree_r = p2->tree_l;
  216.                     p2->tree_l = *ppr;
  217.  
  218.                     if (p2->tree_b == 1)
  219.                         (*ppr)->tree_b = -1;
  220.                     else
  221.                         (*ppr)->tree_b = 0;
  222.  
  223.                     if (p2->tree_b == -1)
  224.                         p1->tree_b = 1;
  225.                     else
  226.                         p1->tree_b = 0;
  227.  
  228.                     *ppr = p2;
  229.                 } /*else*/
  230.                 (*ppr)->tree_b = 0;
  231.                 *pi_balance = FALSE;
  232.             } /*switch*/
  233.         } /*if*/
  234.         EXITV
  235.     } /*if*/
  236.  
  237.     /* not less, not more: this is the same key!  replace...
  238.      */
  239.     MSG("I found it!  Replacing data value")
  240.     *pi_balance = FALSE;
  241.     if (pfi_delete)
  242.         (*pfi_delete)((*ppr)->tree_p);
  243.     (*ppr)->tree_p = pc_data;
  244.     EXITV
  245. }
  246.  
  247.  
  248. int tree_delete(ppr_p, pfi_compare, pc_user, pfi_uar)
  249. tree    **ppr_p;
  250. int    (*pfi_compare)();
  251. char    *pc_user;
  252. int    (*pfi_uar)();
  253. {
  254.     int    i_balance = FALSE, i_uar_called = FALSE;
  255.  
  256.     ENTER("tree_delete");
  257.     EXIT(delete(ppr_p, pfi_compare, pc_user, pfi_uar,
  258.                 &i_balance, &i_uar_called))
  259. }
  260.  
  261.  
  262. static int delete(ppr_p, pfi_compare, pc_user, pfi_uar,
  263.                         pi_balance, pi_uar_called)
  264. tree    **ppr_p;
  265. int    (*pfi_compare)();
  266. char    *pc_user;
  267. int    (*pfi_uar)();
  268. int    *pi_balance;
  269. int    *pi_uar_called;
  270. {
  271.     void    del(), balanceL(), balanceR();
  272.     tree    *pr_q;
  273.     int    i_comp, i_ret;
  274.  
  275.     ENTER("delete")
  276.  
  277.     if (*ppr_p == NULL) {
  278.         MSG("key not in tree")
  279.         EXIT(FALSE)
  280.     }
  281.  
  282.     i_comp = (*pfi_compare)((*ppr_p)->tree_p, pc_user);
  283.     if (i_comp > 0) {
  284.         MSG("too high - scan left")
  285.         i_ret = delete(&(*ppr_p)->tree_l, pfi_compare, pc_user, pfi_uar,
  286.                         pi_balance, pi_uar_called);
  287.         if (*pi_balance)
  288.             balanceL(ppr_p, pi_balance);
  289.     }
  290.     else if (i_comp < 0) {
  291.         MSG("too low - scan right")
  292.         i_ret = delete(&(*ppr_p)->tree_r, pfi_compare, pc_user, pfi_uar,
  293.                         pi_balance, pi_uar_called);
  294.         if (*pi_balance)
  295.             balanceR(ppr_p, pi_balance);
  296.     }
  297.     else {
  298.         MSG("equal")
  299.         pr_q = *ppr_p;
  300.         if (pr_q->tree_r == NULL) {
  301.             MSG("right subtree null")
  302.             *ppr_p = pr_q->tree_l;
  303.             *pi_balance = TRUE;
  304.         }
  305.         else if (pr_q->tree_l == NULL) {
  306.             MSG("right subtree non-null, left subtree null")
  307.             *ppr_p = pr_q->tree_r;
  308.             *pi_balance = TRUE;
  309.         }
  310.         else {
  311.             MSG("neither subtree null")
  312.             del(&pr_q->tree_l, pi_balance, &pr_q, pfi_uar,
  313.                                 pi_uar_called);
  314.             if (*pi_balance)
  315.                 balanceL(ppr_p, pi_balance);
  316.         }
  317.         free(pr_q);
  318.         if (!*pi_uar_called && pfi_uar)
  319.             (*pfi_uar)(pr_q->tree_p);
  320.         i_ret = TRUE;
  321.     }
  322.     EXIT(i_ret)
  323. }
  324.  
  325.  
  326. static void del(ppr_r, pi_balance, ppr_q, pfi_uar, pi_uar_called)
  327. tree    **ppr_r;
  328. int    *pi_balance;
  329. tree    **ppr_q;
  330. int    (*pfi_uar)();
  331. int    *pi_uar_called;
  332. {
  333.     void    balanceR();
  334.  
  335.     ENTER("del")
  336.  
  337.     if ((*ppr_r)->tree_r != NULL) {
  338.         del(&(*ppr_r)->tree_r, pi_balance, ppr_q, pfi_uar,
  339.                                 pi_uar_called);
  340.         if (*pi_balance)
  341.             balanceR(ppr_r, pi_balance);
  342.     } else {
  343.         if (pfi_uar)
  344.             (*pfi_uar)((*ppr_q)->tree_p);
  345.         *pi_uar_called = TRUE;
  346.         (*ppr_q)->tree_p = (*ppr_r)->tree_p;
  347.         *ppr_q = *ppr_r;
  348.         *ppr_r = (*ppr_r)->tree_l;
  349.         *pi_balance = TRUE;
  350.     }
  351.  
  352.     EXITV
  353. }
  354.  
  355.  
  356. static void balanceL(ppr_p, pi_balance)
  357. tree    **ppr_p;
  358. int    *pi_balance;
  359. {
  360.     tree    *p1, *p2;
  361.     int    b1, b2;
  362.  
  363.     ENTER("balanceL")
  364.     MSG("left branch has shrunk")
  365.  
  366.     switch ((*ppr_p)->tree_b)
  367.     {
  368.     case -1: MSG("was imbalanced, fixed implicitly")
  369.         (*ppr_p)->tree_b = 0;
  370.         break;
  371.     case 0:    MSG("was okay, is now one off")
  372.         (*ppr_p)->tree_b = 1;
  373.         *pi_balance = FALSE;
  374.         break;
  375.     case 1:    MSG("was already off, this is too much")
  376.         p1 = (*ppr_p)->tree_r;
  377.         b1 = p1->tree_b;
  378.         if (b1 >= 0) {
  379.             MSG("single RR")
  380.             (*ppr_p)->tree_r = p1->tree_l;
  381.             p1->tree_l = *ppr_p;
  382.             if (b1 == 0) {
  383.                 MSG("b1 == 0")
  384.                 (*ppr_p)->tree_b = 1;
  385.                 p1->tree_b = -1;
  386.                 *pi_balance = FALSE;
  387.             } else {
  388.                 MSG("b1 != 0")
  389.                 (*ppr_p)->tree_b = 0;
  390.                 p1->tree_b = 0;
  391.             }
  392.             *ppr_p = p1;
  393.         } else {
  394.             MSG("double RL")
  395.             p2 = p1->tree_l;
  396.             b2 = p2->tree_b;
  397.             p1->tree_l = p2->tree_r;
  398.             p2->tree_r = p1;
  399.             (*ppr_p)->tree_r = p2->tree_l;
  400.             p2->tree_l = *ppr_p;
  401.             if (b2 == 1)
  402.                 (*ppr_p)->tree_b = -1;
  403.             else
  404.                 (*ppr_p)->tree_b = 0;
  405.             if (b2 == -1)
  406.                 p1->tree_b = 1;
  407.             else
  408.                 p1->tree_b = 0;
  409.             *ppr_p = p2;
  410.             p2->tree_b = 0;
  411.         }
  412.     }
  413.     EXITV
  414. }
  415.  
  416.  
  417. static void balanceR(ppr_p, pi_balance)
  418. tree    **ppr_p;
  419. int    *pi_balance;
  420. {
  421.     tree    *p1, *p2;
  422.     int    b1, b2;
  423.  
  424.     ENTER("balanceR")
  425.     MSG("right branch has shrunk")
  426.     switch ((*ppr_p)->tree_b)
  427.     {
  428.     case 1:    MSG("was imbalanced, fixed implicitly")
  429.         (*ppr_p)->tree_b = 0;
  430.         break;
  431.     case 0:    MSG("was okay, is now one off")
  432.         (*ppr_p)->tree_b = -1;
  433.         *pi_balance = FALSE;
  434.         break;
  435.     case -1: MSG("was already off, this is too much")
  436.         p1 = (*ppr_p)->tree_l;
  437.         b1 = p1->tree_b;
  438.         if (b1 <= 0) {
  439.             MSG("single LL")
  440.             (*ppr_p)->tree_l = p1->tree_r;
  441.             p1->tree_r = *ppr_p;
  442.             if (b1 == 0) {
  443.                 MSG("b1 == 0")
  444.                 (*ppr_p)->tree_b = -1;
  445.                 p1->tree_b = 1;
  446.                 *pi_balance = FALSE;
  447.             } else {
  448.                 MSG("b1 != 0")
  449.                 (*ppr_p)->tree_b = 0;
  450.                 p1->tree_b = 0;
  451.             }
  452.             *ppr_p = p1;
  453.         } else {
  454.             MSG("double LR")
  455.             p2 = p1->tree_r;
  456.             b2 = p2->tree_b;
  457.             p1->tree_r = p2->tree_l;
  458.             p2->tree_l = p1;
  459.             (*ppr_p)->tree_l = p2->tree_r;
  460.             p2->tree_r = *ppr_p;
  461.             if (b2 == -1)
  462.                 (*ppr_p)->tree_b = 1;
  463.             else
  464.                 (*ppr_p)->tree_b = 0;
  465.             if (b2 == 1)
  466.                 p1->tree_b = -1;
  467.             else
  468.                 p1->tree_b = 0;
  469.             *ppr_p = p2;
  470.             p2->tree_b = 0;
  471.         }
  472.     }
  473.     EXITV
  474. }
  475.  
  476.  
  477. int tree_trav(ppr_tree, pfi_uar)
  478. tree    **ppr_tree;
  479. int    (*pfi_uar)();
  480. {
  481.     ENTER("tree_trav")
  482.  
  483.     if (!*ppr_tree)
  484.         EXIT(TRUE)
  485.  
  486.     if (!tree_trav(&(**ppr_tree).tree_l, pfi_uar))
  487.         EXIT(FALSE)
  488.     if (!(*pfi_uar)((**ppr_tree).tree_p))
  489.         EXIT(FALSE)
  490.     if (!tree_trav(&(**ppr_tree).tree_r, pfi_uar))
  491.         EXIT(FALSE)
  492.     EXIT(TRUE)
  493. }
  494.  
  495.  
  496. void tree_mung(ppr_tree, pfi_uar)
  497. tree    **ppr_tree;
  498. int    (*pfi_uar)();
  499. {
  500.     ENTER("tree_mung")
  501.     if (*ppr_tree)
  502.     {
  503.         tree_mung(&(**ppr_tree).tree_l, pfi_uar);
  504.         tree_mung(&(**ppr_tree).tree_r, pfi_uar);
  505.         if (pfi_uar)
  506.             (*pfi_uar)((**ppr_tree).tree_p);
  507.         free(*ppr_tree);
  508.         *ppr_tree = NULL;
  509.     }
  510.     EXITV
  511. }
  512.